package 中等;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 打家劫舍系列问题 {
    private static int[] arr;
    private static int n =0;

    public static void main(String[] args) {
        int[] nums = {1,2,3,1};
        System.out.println(rob2_1(nums));
    }

    //加个字典
    public static int rob1_1(int[] nums) {
        arr = new int[nums.length];
        Arrays.fill(arr,-1 );
        return dp1_1(nums,0);
    }

    private static int dp1_1(int[] nums,int start){
        if (start>=nums.length){
            System.out.println(n++);
            return 0;
        }
        if (arr[start]!=-1){
            System.out.println(n++);
            return arr[start];
        }
        int res = Math.max(dp1_1(nums, start + 1), nums[start] + dp1_1(nums, start + 2));
        arr[start] = res;
        return res;
    }

    //自下向上的解法
    public static int rob1_2(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len+2];
        for (int i = len-1; i >= 0; i--) {
            dp[i] = Math.max(dp[i+1],nums[i]+dp[i+2] );
        }
        return dp[0];
    }

    //自下向上的解法,并且空间复杂度为O(1)
    public static int rob1_3(int[] nums) {
        //第i+1天的最多能偷的钱
        int dp_i_1 = 0;
        //第i+2天的最多能偷的钱
        int dp_i_2 = 0;
        int dp_i = 0 ;
        int n = nums.length;
        for (int i = n - 1; i >= 0; i--) {
            dp_i = Math.max(dp_i_1,nums[i]+dp_i_2 );
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;

    }

    //村子是个环形的,即第一个和最后一个也相连
    public static int rob2_1(int[] nums) {
        if (nums.length<2){
            return nums[0];
        }
        int length = nums.length;
        return Math.max(dp2_1(nums,0 ,length-2 ), dp2_1(nums,1 ,length-1 ));

    }

    private static int dp2_1(int[] nums,int start,int end){
        //第i+1天的最多能偷的钱
        int dp_i_1 = 0;
        //第i+2天的最多能偷的钱
        int dp_i_2 = 0;
        int dp_i = 0 ;

        for (int i = end; i >= start; i--) {
            dp_i = Math.max(dp_i_1,nums[i]+dp_i_2 );
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }

    private static Map<TreeNode,Integer> map = new HashMap<>();

    //村民的房子是树
    public static int rob3_1(TreeNode root) {
        if (root==null){
            return 0;
        }
        if (map.containsKey(root)){
            return map.get(root);
        }
        int i = root.left == null ? 0 : rob3_1(root.left.right) + rob3_1(root.left.left);
        int j = root.right == null ? 0 : rob3_1(root.right.right) + rob3_1(root.right.left);
        int do_it = root.val + i+j;
        int not_do_it = rob3_1(root.left)+rob3_1(root.right);
        int max = Math.max(do_it, not_do_it);
        map.put(root,max );
        return max;

    }

    public static int rob3_2(TreeNode root) {
        int[] res = dp3_2(root);

        return Math.max(res[0],res[1] );

    }

    public static int[] dp3_2(TreeNode root){
        if (root==null){
            return new int[]{0,0};
        }
        int[] right = dp3_2(root.right);
        int[] left = dp3_2(root.left);
        int[] res = new int[2];
        //这家不偷,下家抢不抢,看收益
        res[0] = Math.max(right[0],right[1] )+Math.max(left[0],left[1] );
        //z这家抢,下家就不能抢
        res[1] = right[0] + left[0]+root.val;
        return res;
    }


}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode next;
     TreeNode(int x) { val = x; }

    public TreeNode() {
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                ", next=" + next +
                '}';
    }
}
